package com.leetcode.study.suixianglu;

/**
 * 八皇后
 */
public class EightQueens {

    /**
     * 1、定义一个棋盘以及棋盘的大小
     */
    private static final int SIZE = 8;
    private static final int[][] BOARD = new int[SIZE][SIZE];

    /**
     * 解法数量计数器
     */
    private static int solutionCount = 0;

    public static void main(String[] args) {
        solve(0);
        System.out.println("总解法数: " + solutionCount);
    }


    /**
     * 用来放每一行的皇后。 <br/>
     * 使用for循环解决每列可以放的皇后，使用递归解决每行可以放的操作。
     *
     * @param row
     */
    private static void solve(int row) {

        // 递归的出口（终止条件）：如果已经遍历到最后的叶子节点的下一个叶子节点了
        // 说明到底了，即可以终止了
        if (row == SIZE) {
            printBoard();
            solutionCount++;
            return;
        }

        // 递归体：
        // 要判断此行上的每一个列是否可以放皇后
        for (int col = 0; col < SIZE; col++) {
            if (isSafe(row, col)) {
                // 放皇后
                BOARD[row][col] = 1;
                // 递归到下一行判断
                solve(row + 1);
                // 不符合条件要回溯，把放的皇后撤掉
                BOARD[row][col] = 0;
            }
        }

    }


    /**
     * 判断当前位置是否安全可以放皇后
     * @param row
     * @param col
     * @return
     */
    private static boolean isSafe(int row, int col) {

        // 因当前行是新放的，并不需要判断行是否满足条件
        // 判断当前列是否可以放
        for (int i = 0; i < SIZE; i++) {
            if (BOARD[i][col] == 1) {
                return false;
            }
        }

        // 左上角的对角线是否满足可放
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (BOARD[i][j] == 1) {
                return false;
            }
        }

        // 右上角的对角线是否满足可放
        for (int i = row, j = col; i >= 0 && j < SIZE; i--, j++) {
            if (BOARD[i][j] == 1) {
                return false;
            }
        }

        return true;
    }

    private static void printBoard() {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                // 打印当前位置的状态
                System.out.print(BOARD[i][j] + " ");
            }
            // 换行
            System.out.println();
        }
        // 解法之间空一行
        System.out.println();
    }

}
